package linkedList.分离合并;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 分隔链表725.java
 * @Description TODO https://leetcode-cn.com/problems/split-linked-list-in-parts/
 * @createTime 2021年03月16日 11:08:00
 */
public class 分隔链表725 extends BaseLinkedListTest {

    /**
     * 给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
     * <p>
     * 每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
     * <p>
     * 这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
     * <p>
     * todo 1. 计算能分隔为多少组 2. 进行分隔   不能直接按照k个进行分隔因为可能存在k大于链表长度的情况，这种情况下比如 1，2，3 而k=6 这个时候按照6来分则不行
     */
    public static ListNode[] splitListToParts(ListNode root, int k) {
        int length = 0;
        ListNode temp = root;
        while (temp != null) {
            temp = temp.next;
            length++;
        }
        // 每组的长度
        int nodeLength = length / k;
        // 多余的节点数量
        int slice = length % k;
        ListNode[] listNodes = new ListNode[k];
        temp=root;
        // 每个链表长度为k
        for (int i = 0; i < k; i++) {
            ListNode pre = new ListNode(0);
            ListNode preTemp = pre;
            // nodeLength + (i < slice ? 1 : 0) 的原因是，因为前面的链表的长度肯定是最长的，如果k小于平分后的剩余次数时候，需要把前面的链表长度增加1
            for (int j = 0; j < nodeLength + (i < slice ? 1 : 0); j++) {
                preTemp = preTemp.next = new ListNode(temp.val);
                if (temp != null){
                    temp = temp.next;
                }
            }
            listNodes[i]=pre.next;
        }
        return listNodes;
    }

    public static void main(String[] args) {
        System.out.println(3 / 5);
    }
}
